package com.ljx.offer;

/**
 * . 斐波那契数列
 * https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/?favorite=xb9nqhhg
 * @author: zhangrunkai
 * @date: 2023/3/11
 */
public class C10_1 {

    /**
     * 使用递归， 会超时
     */
    class Solution0 {
        int mod = 1000000007;
        public int fib(int n) {
            // 如果是1返回1，0返回0
            if (n <=1) return n;
            // 大于1的，f(n) = f(n - 1) + f(n + 1)
            return (fib(n - 1) + fib(n - 2)) % mod;
        }
    }

    /**
     * 使用递归出现超时的原因是因为，小的值会重复被计算
     * 例如 f(5) = f(4) + f(3)
     *          = f(3) + f(2) + f(3)
     *          = ...
     * f(3)的值会被计算多次
     */
    class Solution1 {
        int mod = 1000000007;
        // 使用数组进行存储，将值存起来，防止多次重复计算
        int[] f = new int[200];

        /**
         * 这种方式通过空间换时间。多了一个数组的空间，但是结果很明显，这一次不会超时
         * @param n
         * @return
         */
        public int fib(int n) {
            // 如果是1返回1，0返回0
            if (n <= 1 ) return n;
            // 除了0之外，其他值不能为0， 特殊情况下可能（f(n)为1000000007的整数倍）
            if (f[n] != 0)
                return f[n]; // 该值已经存在，直接进行返回
            // 不存在才进行计算
            f[n] = (int) ((long)(fib(n - 1) + fib(n - 2)) % mod);
            return f[n];
        }
    }

    /**
     * 如何省空间，又能省时间？
     * f(n) = f(n - 1)            + f(n -2)
     *      = f(n - 2) + f(n - 3) + f(n -2)
     *      = 2 * f(n - 2)              + f(n - 3)
     *      = 2 * (f(n - 3) + f(n - 4)) + f(n - 3)
     * 可以看到，每一次可以将f(n) 变成另外两个值
     * 所以可以将数组的空间省下，直接用两个值进行维护就可以了
     * f(n) = a * f(A) + b * f(A - 1)
     */
    class Solution2 {
        int mod = 1000000007;
        public int fib(int n) {
            // 如果是1返回1，0返回0
            if (n < 2) return n;
            // a为f(A)的数量，b为f(A-1)的数量
            // 此时 f(n) = 1 * f(n - 1) + 1 * f(n - 2)。 A = n - 1
            int a = 1, b = 1, t;
            // 当A等于1时， f(n) = a * f(1) + b * f(2) = a
            for (int A = n - 1; A > 1; A --) {
                t = (a + b) % mod;
                b = a;
                a = t;
            }
            // 返回结果 f(n) = a * f(1) + b * f(2) = a * 1 + b * 0 = a;
            return a;
        }
    }

    /**
     * 同上，把A变量干掉
     */
    class Solution3 {
        int mod = 1000000007;
        public int fib(int n) {
            // 如果是1返回1，0返回0
            if (n < 2) return n;
            // a为f(A)的数量，b为f(A-1)的数量
            // 此时 f(n) = 1 * f(n - 1) + 1 * f(n - 2)。 A = n - 1
            int a = 1, b = 1, t;

            // 干掉A变量，更优雅一点
//            for (int A = n - 1; A > 1; A --) {
//
//                // fn = fn-1 + fn-2
//                t = (a + b) % mod;
//                b = a;
//                a = t;
//            }
            // 此处，细节的在于 --n
            while (--n > 1) {
                // fn = fn-1 + fn-2
                t = (a + b) % mod;
                b = a;
                a = t;
            }
            return a;
        }
    }


    public static void main(String[] args) {
//        System.out.println(new Solution().fib(5));
    }
}
